package practice;


public class DividingIntegers {
    /**
     * 将整数n分成份，且每份不能为空，任意两份不能相同(不考虑顺序)例如:n=7，k3，下面三种分法被认为是相同的。1，1，5;1，5，1;5，1，1;问有多少种不同的分法*/
    public static void main(String[] args) {
        int n = 7;
        int k = 3;
        int result = countPartitions(n, k);
        System.out.println("不同的分法数量为：" + result);
    }

    public static int countPartitions(int n, int k) {
        if (n <= 0 || k <= 0) {
            return 0;
        }

        // 创建一个二维数组来存储计算结果，dp[i][j]表示将整数i分成j份的方案数
        int[][] dp = new int[n + 1][k + 1];

        // 初始化边界条件
        for (int i = 0; i <= n; i++) {
            dp[i][1] = 1; // 只有一份的情况下，只有一种分法
        }

        // 计算动态规划表格
        for (int i = 2; i <= n; i++) {
            for (int j = 2; j <= k; j++) {
                if(i < j)
                    dp[i][j] = dp[i][i];
                else
                    dp[i][j] = dp[i-1][j - 1] + dp[i - j][j];
            }
        }

        return dp[n][k];
    }
}
